package bhwz.seac3.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class MostK {
	
	private List<ComparableData> data;
	private int k;
	
	public MostK(int k,List<ComparableData> list){
		this.k=k;
		this.data=list;
	}
	
	public List<ComparableData> getMostK(){
		MostK m=new MostK(k,data);
		MostK.Heap h=m.new Heap(k);
		List<ComparableData> list=h.process();
		if(list.size()!=k){
			return null;
		}
		return list;
	}

	public List<ComparableData> getMostK(List<ComparableData> data,int k){
		return null;
	}
	
	
	private class Heap{
		
		private ComparableData[] array; 
		private int k;
		private int size;
		
		Heap(int k){
			size=0;
			this.k=k;
			array=new ComparableData[k+1];
		}
		
		public List<ComparableData> process(){
			if(data==null||data.size()==0){
				return null;
			}
			if(data.size()<=k){
				for(int i=0;i<data.size();i++){
					insert(data.get(i));
				}
			}else{
				int i=0;
				for(;i<k;i++){
					insert(data.get(i));
				}
				for(;i<data.size();i++){
                    insert(data.get(i));
                    deleteMin();
				}
			}
			List<ComparableData> list=new ArrayList<ComparableData>();
			for(int i=0;i<k;i++){
				list.add(array[i]);
			}
            Collections.sort(list);		
            Collections.reverse(list);
			return list;
		}
		
		public void insert(ComparableData x){
			int hole=size;
			for(;(hole+1)/2-1>=0&&array[(hole+1)/2-1].compareTo(x)>0;hole=(hole+1)/2-1){
                array[hole]=array[(hole+1)/2-1];
			}			
			size++;
			array[hole]=x;
		} 
		
		public void deleteMin(){
			int hole=0;
			ComparableData x=array[size-1];
			while(true){
				if(hole*2+2<size){
					if(array[hole*2+1].compareTo(array[hole*2+2])<0){
						if(x.compareTo(array[hole*2+1])<=0){
							break;
						}else{
						   array[hole]=array[hole*2+1];
						   hole=hole*2+1;
						}
					}else{
						if(x.compareTo(array[hole*2+2])<=0){
							break;
						}else{
							array[hole]=array[hole*2+2];
							hole=hole*2+2;
						}
					}
				}else if(hole*2+1<size){
					if(x.compareTo(array[hole*2+1])<=0){
						break;
					}else{
						array[hole]=array[hole*2+1];
						break;
					}
				}else{
					break;
				}
			}
			array[hole]=x;
			size--;
		}
				
	}

}
